
#include<iostream>
#include<algorithm>
using namespace std;

template<class Comparable>
class BinarySearchTree
{
public:
	BinarySearchTree() :root{ nullptr } {};
	BinarySearchTree(const BinarySearchTree& rhs) :root{ nullptr }
	{
		root = clone(rhs.root);
	}
	BinarySearchTree(BinarySearchTree&& rhs) :root{ nullptr }
	{
		root = clone(rhs.root);
	}
	~BinarySearchTree()
	{
		makeEmpty();
	}
	//find the minest number of the subtree which determined by the root
	const Comparable& findMin()const
	{
		return findMin(root)->element;
	}
	const Comparable& findMax()const
	{
		return findMax(root)->element;
	}
	bool contains(const Comparable& x)const
	{
		return contains(x, root);
	}
	bool isEmpty()const
	{
		if (root == nullptr)return true;
		else return false;
	}
	void printTree(ostream& out = cout)const
	{
		if (isEmpty())out << "empty" << endl;
		else {
			printTree(root, out);
		}
	}

	void makeEmpty()
	{
		makeEmpty(root);
	}
	void insert(const Comparable& x)
	{
		insert(x, root);
	}
	void insert(Comparable&& x)
	{
		insert(x, root);
	}
	void remove(const Comparable& x)
	{
		remove(x, root);
	}

	BinarySearchTree& operator = (const BinarySearchTree& rhs)
	{
		if (this != rhs) {
			makeEmpty();
			root = clone(rhs.root);
		}
		return *this;
	}
	BinarySearchTree& operator=(BinarySearchTree&& rhs)
	{
		if (this != rhs) {
			makeEmpty();
			root = clone(rhs.root);
		}
		return *this;
	}

private:
	struct BinaryNode
	{
		Comparable element;
		BinaryNode* left;
		BinaryNode* right;

		//copy 
		BinaryNode(const Comparable& theElement, BinaryNode* lt, BinaryNode* rt) :element{ theElement }, left{ lt }, right{ rt }{};
		//define
		BinaryNode(Comparable& theElement, BinaryNode* lt, BinaryNode* rt) :element{ std::move(theElement) }, left{ lt }, right{ rt }{};
	};
	BinaryNode* root;

	void insert(const Comparable& x, BinaryNode*& t)
	{
		if (t == nullptr)t = new BinaryNode(x, nullptr, nullptr);
		else if (x < t->element)return insert(x, t->left);
		else if (x > t->element)return insert(x, t->right);
		else;
	}
	void insert(Comparable&& x, BinaryNode*& t)
	{
		if (t == nullptr)t = new BinarySearchTree(std::move(x), nullptr, nullptr);
		else if (x < t->element)return insert(std::move(x), t->left);
		else if (x > t->element)return insert(std::move(x), t->right);
		else;
	}
	void remove(const Comparable& x, BinaryNode*& t)
	{
		if (t == nullptr)return;
		else if (x < t->element)return remove(x, t->left);
		else if (x > t->element)return remove(x, t->right);
		else if (t->left != nullptr && t->right != nullptr) {
			t->element = findMin(t)->element;
			remove(t->element, t->right);
		}
		else {
			BinaryNode* oldNode = t;
			t = (t->left == nullptr) ? t->right : t->left;
			delete oldNode;
		}
	}
	BinaryNode* findMin(BinaryNode* t)const
	{
		if (t == nullptr)return nullptr;
		if (t->left == nullptr)return t;
		else return findMin(t->left);
	}
	BinaryNode* findMax(BinaryNode* t)const
	{
		if (t == nullptr)return nullptr;
		if (t->right == nullptr)return t;
		else return findMin(t->right);
	}
	bool contains(const Comparable& x, BinaryNode* t)const
	{
		if (t == nullptr)return false;
		else if (x < t->element)return contains(x, t->left);
		else if (x > t->element)return contains(x, t->right);
		else return true;
	}
	void makeEmpty(BinaryNode*& t)
	{
		if (t != nullptr) {
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		t = nullptr;
	}
	void printTree(BinaryNode* t, ostream& out = cout)const
	{
		if (t != nullptr) {
			printTree(t->left, out);
			out << t->element << " ";
			printTree(t->right, out);
		}
	};
	BinaryNode* clone(BinaryNode* t)const
	{
		if (t == nullptr)return nullptr;
		else return new BinaryNode{ t->element, clone(t->left), clone(t->right) };
	};
};

